import javax.management.MBeanAttributeInfo;
import java.util.Arrays;
import java.util.Locale;
import java.util.Scanner;
import java.util.Scanner;

class Base {

    private int x;
    private int y;

    public Base(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

}

class Sub extends Base {

    private int z;

    public Sub(int x, int y, int z) {
        //write your code here
        super(x, y);
        this.z = z;
    }

    public int getZ() {
        return z;
    }

    public int calculate() {
        return super.getX() * super.getY() * this.getZ();
    }
}

class text {
    public static int removeElement(int[] nums, int val) {
        int count = 0;
        Arrays.sort(nums);
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                index = i;
                break;
            }
        }
        int right = nums.length - 1;
        for (int i = index; i < nums.length; i++) {
            if (i >= right) {
                break;
            }
            if (nums[i] == val) {
                int tmp = nums[i];
                nums[i] = nums[right];
                nums[right--] = tmp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                break;
            }
            count++;
        }
        System.out.println(Arrays.toString(nums));
        return count;

    }

    public static void mairn(String[] args) {
//        int[] arr = {1, 1, 2};
        int[] arr = {1, 1, 2,3,4,5,6,7,7,8,9};
        System.out.println(removeDuplicates(arr));

    }
    public static int removeDuplicates(int[] nums) {
        int slow = 0;
        for (int faster = 0; faster < nums.length; faster++) {
            if (nums[slow] < nums[faster]) {
                slow++;
                nums[slow] = nums[faster];
            }
        }
        System.out.println(Arrays.toString(nums));
        return slow + 1;
    }

    static int hh(int[] nums,int val){
        int slowIndex=0;
        for(int fastIndex =0;fastIndex<nums.length;fastIndex++){
            if(nums[fastIndex]!=val){
                nums[slowIndex]=nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }

    public static void mainm(String[] args) {
//        int[] arr = {0,1,2,2,3,0,4,2};
        int[] arr = {3,2,2,3};
//        int[] arr = {0,1,};
        System.out.println(removeElement(arr, 3));
    }
}

class one {
    private String j;
    public one(String name) {
        this.j = name;
    }

    public String get_j() {
        return j;
    }
}
class two extends one{
    public two(String hh) {
        super(hh);
    }
}
    public class work {
        public static int missNumber(int[] num) {
            int n = num.length;
            double Num = (n/2.0) * (n + 1);
            for (int i = 0; i < num.length; i++) {
                Num -= num[i];
            }
            return (int) Num;
        }

        public static int[] swap(int[] arr, int k) {
            int[] tmp = new int[arr.length];
            int right = arr.length - 1;
            int left = k-1;
            for (int i = 0; i < k; i++) {
                if (left < 0) {
                    break;
                }
                tmp[left--] = arr[right--];
            }
            int i = 0;
            for (int j = k; j < arr.length; j++) {
                tmp[j] = arr[i++];
            }
//            arr = tmp;
            arr = Arrays.copyOf(tmp, tmp.length);
            return arr;
        }

        public static void maddin(String[] args) {
            int[] arr = {1, 2, 3, 4, 5};
            arr = swap(arr, 3);
            System.out.println(Arrays.toString(arr));
            //            int[] n1 = { 0,1,2, 3, 4,5 ,6,7,8,9 };
//            System.out.println(missNumber(n1));
            System.out.println(3 % 5);
        }


        public static one fun() {
            return new two("hh");
        }

        static Boolean fun(String str) {
            if (str.isEmpty() || str.isBlank()) {
                return true;
            }
            str.trim();
            str = str.toLowerCase();
            char[] arr = str.toCharArray();
            char[] ed = new char[arr.length];
            int count = 0;
            for (int i = 0; i < arr.length; i++) {//去除空格
                if (arr[i] <= 'Z' && arr[i] >= 'A'||arr[i] <= 'z' && arr[i] >= 'a' || arr[i] >= '0' && arr[i] <= '9') {
                    ed[count++] = arr[i];
                }
            }
//            if (count == 0) {
//                return true;
//            }
            System.out.println(Arrays.toString(ed));
            int tmp = count-1;
            int i = 0;
            while(i< tmp) {
                if (ed[i++] != ed[tmp--]) {
                    return false;
                }
            }
            return true;
        }

        public static void main11(String[] args) {
            System.out.println("那么好");
        }
        public static void mainn(String[] args) {
            //判断是否是回文
//            System.out.println(fun("A man, a plan, a canal: Panama"));
//            System.out.println(fun("        "));
//            System.out.println(fun(""));
            System.out.println(fun("aa"));
            System.out.println(fun("."));
//            System.out.println(fun("."));
        }
        public static void mainnm(String[] args) {
            //合并俩有序数组
            int[] one = {4, 5, 7, 80, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
            int[] two = {446,7896,754,87654,7908};
            Arrays.sort(two);
            int m = 4,n = two.length,count = 0;
            for (int i = 0; i < m; i++) {//one
                for (int j = count; j < n; j++) {//two
                    if (two[j] > one[i] && two[j] < one[i + 1]) {//插入后面
                        for (int k = m; k > i; k--) {
                            one[k + 1] = one[k];
                        }
                        one[i+1] = two[j];
                        m++;i++;count++;
                    } else if (two[j] <= one[i]) {//插入前面
                        for (int k = m; k >= i; k--) {
                            one[k + 1] = one[k];
                        }
                        one[i] = two[j];
                        m++;i++;count++;
                    } else {
                        break;
                    }
                }
            }
            if (count != n) {
                m++;
                for (int j = count; j < n; j++) {
                    one[m++] = two[j];
                }
            }
            System.out.println(Arrays.toString(one));
        }
        public static void mainaaa(String[] args) {

            String i = "wechatQQWECHATqqhadage";
            char[] arr = new char[100];
            int count = 0;
            int flag = 1;
            for (int j = 0; j < i.length(); j++) {
                flag = 1;
                for (int k = 0; k < count; k++) {
                    if (i.charAt(j) == arr[k]) {
                        flag = 0;
                    }
                }
                System.out.print(i.charAt(j)+"  ");
                if (flag == 1) {
                    arr[count++] = i.charAt(j);
                }
            }
            String ed = "";
            for (int f = 0; f < count; f++) {
                ed += arr[f];
            }
            System.out.println("\n"+ed);
        }
        public static void manin(String[] args) {
            // | ^ &
            // | 有1为1
            int a = 10;//1001
            int b = 12;//1010
            int c = 14;//1110
            System.out.println(a | b);//1011
            System.out.println(a | c);//1011
            int d = -1;//
            System.out.println(~d);//符号位也变

        }
        public static void mainnn(String[] args) {
            Double a = 10.5;
            System.out.println(a % 2);
            a*=-1;
            System.out.println(a % 2);
            System.out.println(a % 0.5);
        }
        public static void ccmain(String[] args) {
            int i = 0;
            if (i == 1)
                System.out.println("ss");
                System.out.println("dd");
                System.out.println("aa");
            if (i != 1)
                System.out.println("dd");
                System.out.println("aa");
                System.out.println("df");
        }
        public static void massin(String[] args) {
            one h = new one("dd");
            one work = fun();
            System.out.println(work.get_j());
        }
        public static void maintt   (String[] args) {
            int[] arr = new int[10];
            System.out.println(arr.length);
            for (int i = 0; i < 10; i++) {
                arr[i] = i;
            }
            System.out.println(Arrays.toString(arr));
            System.out.println("\n");
            int[] newarr;
            newarr = Arrays.copyOf(arr,30);
            for (int i = 10; i < 30; i++) {
                newarr[i] = i;
            }
            for (int x:newarr
                 ) {
                System.out.print(x);
            }
            System.out.println("\n");
            System.out.println(arr.length);
        }
        public static void mainaa(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
                int x = scanner.nextInt();
                int y = scanner.nextInt();
                int z = scanner.nextInt();
                Sub sub = new Sub(x, y, z);
                System.out.println(sub.calculate());
            }
        }


        public static void mainuu(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
                int x = scanner.nextInt();
                int y = scanner.nextInt();
                Data data = new Data(x, y);
                System.out.println(data.getX() + data.getY());
            }
        }

    }
    class Data {

        private int x;
        private int y;

        public Data(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

class Wow {

    public static void main(String[] args) {
        String h = "{{}[]()}";
        System.out.println(h.replace("ff", "qq"));
        for (int i = 0; i < h.length(); i++) {
            h = ((h.replace("{}", "")).replace("()", "")).replace("[]", "");
        }
        System.out.println(h);
    }
    public static void mainm1(String[] args) {
        int[] arr = {3,2,4};
        System.out.println(Arrays.toString(twoSum(arr, 6)));
        int add = twoSum(arr,3).hashCode();
        System.out.println(add); 
    }

    Boolean is_viual(String s) {
        int length = s.length() / 2;
        for (int i = 0; i < length; i++) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }

        return s.length() == 0;
    }
    public static int[] twoSum(int[] nums, int target) {
    int[] ed = new int[2];
        int i = 0;
        for (; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    ed[0] = i;
                    ed[1] = j;
                    return ed;
                }
            }
        }
        return ed;

    }
        public static void mainm(String[] args) {
//        System.out.println(isPalindrome(" amanaplanacanalpanama  "));
//        System.out.println(isPalindrome("race a car"));
//        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
//        System.out.println(Str());
        String arr = "aaaaaaaba";
        char[]arr1 = arr.toCharArray();
        Arrays.sort(arr1);
        System.out.println(arr1);
        //  System.out.println(Arrays.toString(arr1));
//        System.out.println(arr2.toString());
        for (int i = 0; i < arr.length(); i++) {
            int j = arr.indexOf(arr.charAt(i));
            int k = arr.lastIndexOf(arr.charAt(i));
            if (i == k) {
                System.out.println(i);
            }
            while(i + 1 == k) {
                i = k;
            }
        }
        System.out.println(-1);
    }

    public static void Str1() {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();

        String[] arr = s.split(" ");
        System.out.println(arr[arr.length - 1].length());

    }
//hello nowcoder
    public static int Str() {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        System.out.println(s);//得到字符串

        int slow = 0;
        int faster = 0;
        for (;faster < s.length(); faster++) {
            if(s.charAt(faster) == ' '){
              slow = faster;
            }
        }
            return faster-slow-1;
    }

    public static boolean isPalindrome(String s) {
        s.trim();
        s = s.toLowerCase(Locale.ROOT);
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) <= 'z' && s.charAt(i) >= 'a') {
                str.append(s.charAt(i));
            }
        }
        StringBuilder Str1 = new StringBuilder(str);
        StringBuilder Str2 = new StringBuilder(str);
        System.out.println(Str2);
        if (Str2.compareTo(Str1.reverse()) == 0) {
            return true;
        } else {
            return false;
        }

    }

    public boolean hasCircol(My) {

    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = nums1.length - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        if (j >= 0) {
            for (int l = 0; l <= j; l++) {
                nums1[l] = nums2[l];
            }
        }
        System.out.println(Arrays.toString(nums1));
    }

    public static void main_666(String[] args) {
        int[] arr1 = {0, 0, 0};
        int[] arr2 = {};
        merge(arr1, 0, arr2, 0);
    }
}